#include <stdio.h>

#define MaxSize 255

// 串的顺序存储结构
typedef struct {
    char ch[MaxSize];   // ch[0]弃用
    int lenth;          // 单独定义lenth存储字符串长度，防止长度超过255（4个字节）
} SString;

/**
 * 字符串初始化
 *
 * @return
 */
SString InitString() {
    SString S;
    S.lenth = 0;
    return S;
}

/**
 * 打印字符串S
 *
 * @param S
 */
void PrintString(SString S) {
    if (S.lenth > 0) {
        for (int i = 1; i <= S.lenth; ++i) {
            printf("%c", S.ch[i]);
        }
        printf("\n");
    } else {
        printf("NULL\n");
    }
}

/**
 * 字符入串
 *
 * @param S
 * @param c
 * @return 若成功则返回 true，若失败则返回 false
 */
bool EnterString(SString &S, char c) {
    if (S.lenth + 1 > MaxSize) {
        return false;
    }
    S.ch[++S.lenth] = c;
    return true;
}

/**
 * 用Sub接收串S中第pos个字符起，长度为len的子串。
 *
 * @param Sub
 * @param S
 * @param pos
 * @param len
 * @return 若成功则返回 true，若失败则返回 false
 */
bool SubString(SString &Sub, SString S, int pos, int len) {
    // 判断查询子串位置的合法性
    if (len <= 0 || pos > S.lenth || pos + len - 1 > S.lenth) {
        return false;
    }

    Sub.lenth = len;
    for (int i = 0; i < len; ++i) {
        Sub.ch[i+1] = S.ch[pos+i];
    }
    return true;
}

/**
 * 比较字符串S和T
 *
 * @param S
 * @param T
 * @return
 */
int StrCompare(SString S, SString T) {
    for (int i = 1; i <= S.lenth && i <= T.lenth; ++i) {
        if (S.ch[i] != T.ch[i]) {
            return S.ch[i]-T.ch[i];
        }
    }
    if (S.lenth > T.lenth) {
        return 1;
    } else if (S.lenth < T.lenth) {
        return -1;
    } else {
        return 0;
    }
}

/**
 * 定位子串T在主串S中的位置。
 *
 * @param S
 * @param T
 * @return 若查询到则返回S中第一次出现T的第一个字符到位置，否则返回0
 */
int IndexStr(SString S, SString T) {
    int i = 1;
    int n = S.lenth, m = T.lenth;
    SString sub;    // 暂存子串
    while (i <= n - m + 1) {
        SubString(sub, S, i, m);
        if (StrCompare(sub, T) != 0) {
            i++;
        } else {
            return i;
        }
    }
    return 0;
}

/**
 * 朴素模式匹配算法
 *
 * @param S 主串
 * @param T 模式串
 * @return
 */
int SimplePM(SString S, SString T) {

    int i = 1, j = 1;
    while (i <= S.lenth && j <= T.lenth) {
        if (S.ch[i] == T.ch[j]) {
            // 继续比较后续字符
            ++i;
            ++j;
        } else {
            // 指针后退重新开始匹配
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > T.lenth) {
        return i - T.lenth;
    } else {
        return 0;
    }
}

/**
 * KMP匹配算法
 *
 * @param S 主串
 * @param T 模式串
 * @param next next数组
 * @return
 */
int Index_KMP(SString S, SString T, int next[]) {
    int i = 1, j = 1;
    while (i <= S.lenth && j <= T.lenth) {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            // 继续比较后续字符
            ++i;
            ++j;
        } else {
            // 模式串向右移动
            j = next[j];
        }
    }
    if (j > T.lenth) {
        return i - T.lenth;     // 匹配成功
    } else {
        return 0;
    }
}


int main() {
    // 字符串初始化
    SString S = InitString();
    SString T = InitString();
    // 接收输入的字符
    char c;

    // 输入主串和模式串
    printf("Please enter string S: \n");
    scanf("%c", &c);
    while(c != '\n' && EnterString(S, c)) {
        scanf("%c", &c);
    }
    printf("Please enter string T: \n");
    scanf("%c", &c);
    while(c != '\n' && EnterString(T, c)) {
        scanf("%c", &c);
    }
    PrintString(S);
    PrintString(T);

    // 串的基本操作定位子串
    int indexPos = IndexStr(S, T);
    printf("Basic Operation Result: pos = %d\n", indexPos);
    // 朴素模式匹配
    int simpleMP = SimplePM(S, T);
    printf("Simple Pattern Matching Result: pos = %d\n", simpleMP);

    return 0;
}